/**
 * @file     deleteDuplicates.js
 * @brief    [83. 删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/)
 * @author   Zhu
 * @date     2022-03-18 00:00
 */

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * 快进法
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    let cur = head;
    while (cur) {
        // 快进
        const temp = cur;
        while (cur.next && cur.next.val == cur.val) {
            cur = cur.next;
        }
        temp.next = cur.next;

        cur = cur.next;
    }

    return head;
};

/**
 * 穿针引线
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    let cur = head;
    while (cur?.next) {
        if (cur.next.val === cur.val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }

    return head;
};

/**
 * @file     deleteDuplicates.js
 * @brief    [82. 删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/)
 * @author   Zhu
 * @date     2022-03-18 16:20
 */

/**
 * 每回合保证pre 和 cur 不一样， 然后判断 cur.next
 * - 一样，则快进到不一样的点
 * - 不一样，则确定了保留cur
 * 最后跳出循环后，pre.next = null
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    const vHead = new ListNode(-Infinity, head);

    let pre = vHead;
    let cur = head;
    while (cur) {
        if (cur.next && cur.next.val === cur.val) {
            while (cur.next && cur.next.val === cur.val) {
                cur = cur.next;
            } // 迭代到最后一个重复值
        } else {
            pre.next = cur;
            pre = cur;
        }
        cur = cur.next;
    }

    pre.next = cur;

    return vHead.next;
};

/**
 * 递归
 * @param {ListNode} head
 * @returns {ListNode}
 */
var deleteDuplicates = function (head) {
    const vHead = new ListNode(-Infinity, head);

    if (head === null) return null;
    if (head.next === null) return head;
    if (head.next.val === head.val) {
        while (head.next && head.next.val === head.val) {
            head = head.next;
        }
        vHead.next = deleteDuplicates(head.next);
    } else {
        head.next = deleteDuplicates(head.next);
    }

    return vHead.next;
};
